class Solution
{
public:
    int minScore(int n, vector<vector<int>> &roads)
    {
        vector<vector<pair<int, int>>> adjTable(n + 1);
        for (auto &road : roads)
        {
            adjTable[road[0]].push_back({road[1], road[2]});
            adjTable[road[1]].push_back({road[0], road[2]});
        }
        queue<int> q;
        unordered_map<int, unordered_set<int>> visited;
        visited[1].insert(1);
        q.push(1);
        int minPathScore = INT_MAX;
        while (!q.empty())
        {
            int city = q.front();
            q.pop();
            for (auto nearCity : adjTable[city])
            {
                if (!visited[city].count(nearCity.first) && !visited[nearCity.first].count(city)) // 这里要双向验证，不然重复太多就会超时
                {
                    visited[city].insert(nearCity.first);
                    minPathScore = min(minPathScore, nearCity.second);
                    q.push(nearCity.first);
                }
            }
        }
        return minPathScore;
    }
};